package Hot100;

import common.ListNode;

import java.util.Stack;

/**
 * @author zhangmin
 * @create 2022-01-03 15:57
 */
public class isPalindrome234 {

    /**
     * 234. 回文链表
     * 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
     * 1、转换成数组再判断
     * 2、双指针：找到中间节点，然后翻转前半段，判断前半段后后半段是的相同
     * 3、栈:将节点全部入栈，然后从头开始判断每个节点和出栈元素是否相等
     * 4、递归，
     * */
    public boolean isPalindrome(ListNode head) {
        if(head==null) return false;
        Stack<ListNode> stack=new Stack<>();
        ListNode p=head;
        while (p!=null){
            stack.push(p);
            p=p.next;
        }
        while (head!=null){
            if (head.val!=stack.peek().val)
                return false;
            head=head.next;
            stack.pop();
        }
        return true;
    }


}
